def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:  # 最小规模。直接返回
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i)  # 调用自身   change - i 减小规模： 每次减去一种硬币面值挑选最小数量
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins


#
# print(recMC([1, 5, 10, 25], 63))


def recMC2(coinValueList, change):
    minCoins = change
    if change in coinValueList:  # 最小规模。直接返回
        return 1
    else:
        numlist = []
        for c in coinValueList:
            if c <= change:
                numlist.append(c)

        for i in numlist:
            numCoins = 1 + recMC2(coinValueList, change - i)  # 调用自身   change - i 减小规模： 每次减去一种硬币面值挑选最小数量
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins


# print(recMC2([1, 5, 10, 25], 63))

# 计算运行时间
import time

print(time.clock())
print(recMC([1, 5, 10, 25], 63))
print(time.clock())
